//
//  Trie.hpp
//  DemoV2
//
//  Created by 董一龙 on 2022/8/6.
//

#ifndef Trie_hpp
#define Trie_hpp

#include <unordered_map>
#include <string>
#include <initializer_list>
/// 前缀树
class Trie {
    struct Node {
        std::unordered_map<char, Node*> subNodeMap;
    };
public:
    Trie();
    ~Trie();
    
    /// 向可匹配的前缀集添加前缀
    /// @param prefixPattern 要添加的前缀，例如abc*
    /// 默认星号结尾，不支持星号在中间，没有转义。
    /// 空字符串无效，支持*，意为匹配任何字符串
    void insertPrefix(std::string const& prefixPattern);
    
    /// 向可匹配的前缀集添加多个前缀
    /// @param prefixPatternSet 前缀集合
    void insertPrefixSet(std::initializer_list<std::string> const& prefixPatternSet);
    
    /// 可匹配前缀集中存在某个前缀匹配了输入字符串
    /// @param str 输入字符串，假设输入字符串没有星号。空字符串返回false
    /// @return bool 是否存在前缀匹配
    bool hasPrefixMatch(std::string const& str) const;
private:
    Node *root;
};
#endif /* Trie_hpp */
